A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The copyright owner does not hereby waive any of its rights to have this patent document maintained in secrecy, including without limitation its rights pursuant to 37 C.F.R. xc2xa71.14.
This invention relates to memory management in a computer system, and more particularly to sharing of lookup data by loading lookup data into standard template library objects (STL objects) in a shared memory.
Modern data processing systems that support several processes simultaneously are defined as multiprocessing systems. More specifically, a process can be defined as an address space, a thread of control operating within that address space, and a set of required system resources for supporting the execution of a program. Before execution, the data needed for program execution and on which the program operates is loaded into the address space. In a multiprocessing system, several processes may execute and share data; some of the data used in different processes are the same for subsequent processes, and are termed xe2x80x9cshared data.xe2x80x9d
In multiprocessing systems, a plurality of processes may execute simultaneously for higher performance. The processes may be interconnected by a system bus through which they communicate among themselves and with commonly shared resources, such as input/output units and working memories. Shared memory is a reserved memory area to which all of the sharing processes have access; different access methods allow the processes to use the shared memory with different performance characteristics.
Sharing of data structures between processes, specially the sharing of Standard Template Library object (STL objects), has always been a desirable functionality. The Standard Template Library (STL) comprises a set of C++ generic data structures and algorithms, and the STL provides reusable, interchangeable components adaptable to many different uses in software development environment, some of which are described by G. Bowden Wise in An Overview of the Standard Template Library, available at www.cs.rpi.edu/xcx9cwiseb/xrds/ovp2-3b.html. This article is hereby incorporated by reference in its entirety.
Conventional operating systems such as Windows NT and other operating systems such as UNIX provide shared memory. NT provides shared memory in the form of memory-mapped files. However, the shared memory segment is not necessarily loaded in at the same address by default in different processes or in the same program. Specifically, the MapMemoryFileEx Application Program Interface (API) function is used to request NT to load the shared memory segment at a particular address. It is of very little relevance whether the memory segment is loaded in the same address for offset-based data structures like an array, because, even if the same data structure is loaded at different addresses in different processes, the computations are done based on the offsets. It is of great importance, however, whether the memory segment is loaded in the same address for pointer-based data structures, where an address in one process is not correlated to an address in another process.
STL objects are pointer-based data structures. Addressing the deficiency in the traditional file-based approach, this invention provides a technique to load STL objects to allow sharing of the STL objects by a plurality of processes. In one embodiment, this invention implements sharing of any number of STL objects between processes and threads using New Technology""s (NT""s) Section Objects (or shared memory) and special STL allocator function. Data which are needed by more than one process are stored in user STL objects, and the user STL objects are placed in the same memory segment. By attaching the shared memory segment, multiple processes may have access to the stored data.
In one aspect, the invention features a computer-implemented method or an apparatus comprising a computer-readable medium having a plurality of sequences of instructions stored thereon for sharing data structures among processes by using a shared memory segment. The method includes creating the shared memory segment, anchoring a system STL (Standard Template Library) map in the shared memory segment, receiving a user STL object, obtaining an address for the user STL object, and inserting the user STL object into the system map.
In another aspect, the invention is directed to a method or an apparatus comprising a computer-readable medium having a plurality of sequences of instructions stored thereon for conducting garbage collection by an allocator, the allocator capable of allocating storage for a user STL object in a shared memory segment common to a plurality of processes. The method includes creating a first map containing a plurality of nodes representing a plurality of free blocks, each block represented in the first map by a node denoting a size and an address of the free block, responding to an allocation request, and responding to a deletion request by entering a size and an address of a deleted block into the first map.
In yet another aspect, the invention is directed to a computer system implementing a data-sharing scheme capable of supporting a shared memory segment common to a plurality of processes, the computer having a processor for executing instructions, a memory for storing instructions, the computer system. The computer system includes the shared memory segment, a system STL map anchored in the shared memory segment, and a plurality of user STL objects, wherein each object is named and is seated in the STL map by inserting a name and an address of the object into the system STL map.
Various implementations of the invention may include one or more of the following features. The user STL object may have a name. The shared memory segment may be named and may comprise approximately 10 MB of memory. The user STL object may comprise created or existing user STL object. The obtaining step may consist of returning the address of the user STL object if the name of the user STL object is in the system. STL map. The obtaining step may consist of returning a next allocation address from the shared memory segment if the name of the user STL object is not in the system STL map.
The method may consist of updating the next allocation address by increasing the next allocation address by an allocated size of the user STL object. The inserting step may consist of entering the name and the address of the user STL object into the system STL map.
Further the method may consist of requesting storage from an allocator, wherein the allocator allocates memory from the shared memory segment to store at least one node of the user STL object and data added to the user STL object. The data may comprise an entity capable of supporting a single writer and a plurality of readers. An access to the address of the next allocation may be synchronized. The allocator may performs garbage collection. The processes may be threaded.
Implementation of the invention may include one or more of the following features. The responding to an allocation request step may return an address of a free block in the plurality of free blocks if the allocation request is for a storage size equal to or smaller than the free block. The responding to an allocation request step may allocate memory from the shared memory segment. It may provide a snapshot of the shared memory segment. The snapshot may include a total size of the shared memory segment. The first map may be available to only one process of the plurality of processes and the one process may be a writer process. The shared memory segment may be named and may consist of about 10 MB of memory. Addresses of the plurality of user STL objects may comprise addresses of the STL objects existing in the system STL map, and may comprise next allocation addresses.
An allocator may manage a garbage collection process responding to allocation requests and deletion requests. The allocator may allocate memory from the shared memory segment to store at least one node and data contained in each user STL object. At least one node may contain pointers to accounting information. A first map may contain a first set of nodes denoting sizes and addresses of a plurality of free blocks and a second map containing a second set of nodes representing the addresses of and pointers to the plurality of free blocks in the first map. The allocator may insert a newly-freed block contained in a deletion request into the first map and the second map. The allocator may coalesce the plurality of free blocks in the first map after responding to deletion requests by combining an existing free block in the plurality of free blocks with by an adjacent newly-freed block.
Sharing of STL objects among processes as described herein has one or more of the following advantages. One advantage of this invention is its total portability between different versions of the STL because the invention does not utilize the STL at a source code level. Another advantage of this invention is that it is intuitive and easy to use, requiring no new methods or interfaces for the developer to learn. Yet another advantage of the invention is its ability to store any number of STL objects in one shared memory segment, with the shared memory instrumented to provide various usage details such as total size of the shared memory segment, total number of free blocks in the free store, and the granularity of the free blocks. Furthermore, this invention eliminates any type of same-machine sockets and COM usage, thus freeing valuable resources. As soon as the shared memory is mapped to the requesting process, access to the data is instantaneous. Finally, this invention offers the advantage of freeing the developers from the memory handling details, such as garbage collection.
The primary usage for this invention is for lookup data, where lookup data can be defined as an entity with a single writer and multiple readers. One process, typically an NT service, loads the lookup data and writes the data to the STL objects in shared memory. The data are available to the other processes once the processes load the shared memory.